package util;

/**
 * question: 给一个元素值范围在 0 ~ n 的 数组，求在 0 ~ n 没有出现过的元素
 * <p>
 * examples: 0 ~ 4 -> [1,3,4,3] -> [1,3,3,4] -> 2
 *
 * @author Liaorun
 */
public class PrintNoInArray {

    public static void main(String[] args) {
        printNumberNoInArray(new int[]{1, 3, 4, 3});
    }


    public static void printNumberNoInArray(int[] arr) {

        if (arr == null || arr.length == 0) {
            return;
        }

        for (int value : arr) {
            modify(value, arr);
        }

        for (int i = 0; i < arr.length; i++) {
            if (arr[i] != i + 1) {
                // 没做到的位置，就知道了缺的数字
                System.out.println(i + 1);
            }
        }
    }

    /**
     * 前提： 0 < value <= arr.length,否则会越界
     * 将数组arr中的一个元素值value,放到 index = value - 1 处。
     *
     * @param value 数组中的一个元素
     * @param arr   数组
     */
    private static void modify(int value, int[] arr) {
        // 跳出条件: value 放到了 value - 1 下标出
        while (arr[value - 1] != value) {
            // value 没放到了 value - 1 下标出
            // 取出 index = value - 1位置的数
            int temp = arr[value - 1];
            // 将value 放到 index = value - 1下标处
            arr[value - 1] = value;
            // 原来index = value - 1位置的数作为下一轮的value
            value = temp;
        }
    }
}
